package unionFind;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * 547. 省份数量
 */
public class P547 {
    public int findCircleNum(int[][] isConnected) {
        // 1.初始化并查集表
        int[] unionArray = new int[isConnected.length];
        for (int i = 0; i < unionArray.length; i++) {
            unionArray[i] = i;
        }
        // 2. 遍历循环
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1) {
                    union(unionArray, i, j);
                }
            }
        }
        // 3. 结果
        Set<Integer> unique = new HashSet<>();
        for (int root : unionArray) {
            unique.add(find_father(unionArray, root));
        }
        return unique.size();
    }

    private void union(int[] union, int x, int y) {
        if (x != y) {
            int f_x = find_father(union, x);
            int f_y = find_father(union, y);
            union[f_y] = f_x;
        }
    }

    private int find_father(int[] union, int x) {
        return union[x] == x ? x : find_father(union, union[x]);
    }

    public static void main(String[] args) {
        int[][] isConnected = new int[][]{
                //0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
                {1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
                {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0},
                {1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1},
                {0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}
        };
        int circleNum = new P547().findCircleNum(isConnected);
        System.out.println(circleNum);
    }
}
